#include <iostream>
using namespace std;
#include <vector>
enum State
{
    EMPTY,  // 空
    EXITS,  // 存在
    DELETE, // 删除
};

template <class T>
struct HashData
{
    T _data;
    State _state; // 为了防止找不到后面的元素，所以我们不止要存放数值，还要存放当前下标的状态
};

// 这里我们直接实现kv模型
// k，pair<k,v>
template <class K, class T, class KeyOfT>
class HashTable
{
    typedef HashData<T> HashData;

public:
    // 这里的T表示的是插入数据的类型，可能是pair
    bool insert(const T &x)
    {
        KeyOfT koft;
        // 负载因子=表中数据/表的大小,为了保证hash永远不会满
        if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)
        {
            // 增容
            vector<HashData> newtables;
            ssize_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
            newtables.resize(newsize);
            for (int i = 0; i < _tables.size(); i++)
            {
                if (_tables[i]._state == EXITS)
                {
                    size_t index = koft(_tables[i]._data) % newtables.size();
                    while (newtables[index]._state == EXITS)
                    {
                        ++index;
                        if (index == _tables.size())
                        {
                            index = 0;
                        }
                    }
                    newtables[index] = _tables[i];
                }
            }
            _tables.swap(newtables);
        }

        //KeyOfT koft; // 如果传入的数据是一个pair，那么我们要那它的key去进行计算，而不是整个pair

        // 计算x在表中映射的位置,如果x是一个pair类型的数据，那么我们要取出x中的k
        size_t index = koft(x) % _tables.size();
        // 1：线性探测法
        while (_tables[index]._state == EXITS)
        {
            // 要维护去重的特性
            if (koft(_tables[index]._data) == koft(x))
            {
                return false;
            }
            ++index;
            if (index == _tables.size())
            {
                index = 0;
            }
        }

        _tables[index]._data = x;
        _tables[index]._state = EXITS;
        _num++;

        return true;
    }

    // 查找是通过key去找的
    HashData *find(const K &key)
    {
        KeyOfT koft;
        size_t index = key % _tables.size();
        while (_tables[index]._state != EMPTY)
        {
            if (koft(_tables[index]._data) == key)
            {
                if (_tables[index]._state == EXITS)
                {
                    return &_tables[index];
                }
                else if (_tables[index]._state == DELETE)
                {
                    return nullptr;
                }
            }
            ++index;
            if (index == _tables.size())
            {
                index = 0;
            }
        }
        return nullptr;
    }

    // 删除也是通过key去删除的
    bool erase(const K &key)
    {
        HashData *ret = find(key);
        if (ret)
        {
            ret->_state = DELETE;
            --_num;
            return true;
        }
        else
        {
            return false;
        }
    }

private:
    vector<HashData> _tables;
    size_t _num = 0; // 哈希表中有效的数据个数.
};

